package 数组;

import java.util.Arrays;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/3sum-closest/
 */
public class _16_最接近的三数之和 {

    /**
     * 排序 + 双指针
     * 先将数组排序  然后通过两个指针移动进行比较， 若有相同的值  则跳过 O(n^2)
     * @param nums 目标数组
     * @param target 目标值
     * @return int
     */
    public int threeSumClosestTwo(int[] nums, int target) {
        Arrays.sort(nums);
        int length = nums.length;
        int ret = 10000;

        for (int i = 0; i < length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1, k = length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == target) {
                    return sum;
                }
                if (Math.abs(sum - target) < Math.abs(ret - target)) {
                    ret = sum;
                }

                if (sum < target) {
                    int j1 = j + 1;
                    while (j1 < k && nums[j1] == nums[j]) {
                        ++j1;
                    }
                    j = j1;
                }else {
                    int k1 = k - 1;
                    while (k1 > j && nums[k1] == nums[k]) {
                        --k1;
                    }
                    k = k1;
                }
            }
        }
        return ret;
    }

    /**
     * 暴力解法  O(n^3)
     * @param nums 目标数组
     * @param target 目标值
     * @return int
     */
    public int threeSumClosest(int[] nums, int target) {
        int close = nums[0] + nums[1] + nums[2];
        int min = (close - target) >= 0 ? (close - target) : -(close - target);
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int sum = nums[i] + nums[j] + nums[k];
                    int temp = (sum - target) >= 0 ? (sum - target) : -(sum - target);
                    if (sum - target == 0) {
                        return sum;
                    }
                    if (min > temp) {
                        min = temp;
                        close = sum;
                    }

                }
            }
        }
        return close;
    }
}
